package leetcode.D600.T567;

import java.util.HashMap;
import java.util.Map;

class Solution {
    /*// 一刷
    public boolean checkInclusion(String s1, String s2) {
        Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
        int left = 0, right = 0, valid = 0;
        for(int i=0; i<s1.length(); ++i) {
            char c = s1.charAt(i);
            int origin = need.getOrDefault(c, 0);
            need.put(c, origin+1);
            window.putIfAbsent(c, 0);
        }
        while(right < s2.length()) {
            char c = s2.charAt(right++);
            if(need.containsKey(c)) {
                int origin = window.get(c);
                window.put(c, origin+1);
                if(origin+1 == need.get(c)) {
                    valid++;
                }
            }
            while(valid == need.size()) {
                if(right-left == s1.length()) {
                    return true;
                }
                char d = s2.charAt(left++);
                if(need.containsKey(d)) {
                    int origin = window.get(d);
                    window.put(d, origin-1);
                    if(origin == need.get(d)) {
                        valid--;
                    }
                }
            }
        }
        return false;
    }*/

    // 二刷
    /*public boolean checkInclusion(String s1, String s2) {
        int left = 0, right = 0;
        int valid = 0;
        Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
        for(int i=0; i<s1.length(); ++i) {
            char c = s1.charAt(i);
            int origin = need.getOrDefault(c, 0);
            need.put(c, origin+1);
            window.putIfAbsent(c, 0);
        }
        while(right < s2.length()) {
            char c = s2.charAt(right++);
            if(need.containsKey(c)) {
                int origin = window.get(c);
                if(origin + 1 == need.get(c)) {
                    valid++;
                }
                window.put(c, origin+1);
            }
            while(valid == need.size()) {
                if(right - left == s1.length()) {
                    return true;
                }
                char d = s2.charAt(left++);
                if(need.containsKey(d)) {
                    int origin = window.get(d);
                    if(origin == need.get(d)) {
                        valid--;
                    }
                    window.put(d, origin-1);
                }
            }
        }
        return false;
    }*/

    // 三刷
    /*public boolean checkInclusion(String s1, String s2) {
        int valid = 0, left = 0, right = 0;
        Map<Character, Integer> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for(int i=0; i<s1.length(); ++i) {
            int origin = need.getOrDefault(s1.charAt(i), 0);
            need.put(s1.charAt(i), origin+1);
            window.put(s1.charAt(i), 0);
        }
        while(right < s2.length()) {
            char c = s2.charAt(right++);
            if(need.containsKey(c)) {
                int origin = window.get(c);
                if(origin + 1 == need.get(c)) {
                    valid++;
                }
                window.put(c, origin + 1);
            }
            while(valid == need.size()) {
                if(right - left == s1.length()) {
                    return true;
                }
                char d = s2.charAt(left++);
                if(need.containsKey(d)) {
                    int origin = window.get(d);
                    if(origin == need.get(d)) {
                        valid--;
                    }
                    window.put(d, origin - 1);
                }
            }
        }
        return false;
    }*/

    // 四刷
    public boolean checkInclusion(String s1, String s2) {
        int left=0, right=0, valid=0;
        Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
        for (int i = 0; i < s1.length(); i++) {
            need.put(s1.charAt(i), need.getOrDefault(s1.charAt(i), 0)+1);
        }
        while (right < s2.length()) {
            char c = s2.charAt(right++);
            if (need.containsKey(c)) {
                int origin = window.getOrDefault(c, 0);
                if (origin+1 == need.get(c)) {
                    valid++;
                }
                window.put(c, origin+1);
            } else {
                left = right;
                window.clear();
                valid = 0;
                continue;
            }
            while(valid == need.size()) {
                if (right - left == s1.length()) {
                    return true;
                }
                char d = s2.charAt(left++);
                int origin = window.get(d);
                if (origin == need.get(d)) {
                    valid--;
                }
                window.put(d, origin-1);
            }
        }
        return false;
    }
}
